﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

/// <summary>
/// 路劲总和
/// </summary>
namespace BinarTtree.HasPathSum
{
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
        {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class MainProject
    {
        static void Main(string[] args)
        {
            //TreeNode treeNode = new TreeNode(1, new TreeNode(2, new TreeNode(3, new TreeNode(5), new TreeNode(6)), new TreeNode(4, new TreeNode(6), new TreeNode(5))), new TreeNode(2, new TreeNode(4, new TreeNode(5), new TreeNode(6)), new TreeNode(3, new TreeNode(6), new TreeNode(5))));
            TreeNode treeNode = new TreeNode(5,new TreeNode(4,new TreeNode(11,new TreeNode(7),new TreeNode(2))),new TreeNode(8,new TreeNode(13),new TreeNode(14,null,new TreeNode(1))));
            Console.WriteLine(HasPathSum(treeNode, 22));
            Console.ReadKey();
        }

        public static bool HasPathSum(TreeNode root, int targetSum)
        {
            return Path(root, targetSum, 0);
        }

        public static bool Path(TreeNode treeNode, int targetSum, int relative)
        {
            if (treeNode == null)
                return false;

            relative += treeNode.val;

            if ((treeNode.left == null && treeNode.right == null))
            {
                return relative == targetSum;
            }

            return Path(treeNode.left, targetSum, relative) || Path(treeNode.right, targetSum, relative);

            //if (treeNode.left == null && treeNode.right == null)
            //{
            //    return targetSum == relative;
            //}
            //else if (treeNode.left != null && treeNode.right == null)
            //{
            //    return Path(treeNode.left, targetSum, relative);
            //}
            //else if (treeNode.left == null && treeNode.right != null)
            //{
            //    return Path(treeNode.right, targetSum, relative);
            //}
            //else
            //{
            //    relative += treeNode.val;
            //    return Path(treeNode.left, targetSum, relative) || Path(treeNode.right, targetSum, relative);
            //}

            //if (treeNode==null)
            //{
            //    if (targetSum == relative)
            //    {
            //        return true;
            //    }
            //    return false;
            //}
            //relative += treeNode.val;

            ////if ()
            ////{

            ////}
            //return ((root == treeNode) && root.left == null ? false : Path(treeNode.left, targetSum, relative, root)) ||
            //    ((root == treeNode) && root.right == null ? false : Path(treeNode.right, targetSum, relative, root));

            ////return  || Path(treeNode.right, targetSum, relative, root);
        }
    }
}
